package set.src;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * 
 * @author Erik Sapir & Lior Zibi
 * 
 * Ordered set using coarse-grained synchronization.
 * In this implementation, remove,add and contain operations 
 * are blocking.
 * 
 * @param T Item type.
 */

public class CoarseList<T> implements Set<T> {
	/**
	 * First list Node
	 */
	volatile private Node m_head;

	/**
	 * Synchronizes access to list
	 */
	private Lock m_lock;
  
	/**
	 * number of element in the list
	 */
	private volatile int m_size;
  
	/**
	 * Constructor
	 */
	public CoarseList(int numOfThreads) {
		System.out.println("\n\tSet Is: Coarse List\n");
		 
		// Add sentinels to start and end
		this.m_head  = new Node(Integer.MIN_VALUE);
		this.m_head.m_next = new Node(Integer.MAX_VALUE); 
    
		this.m_lock = new ReentrantLock();
		this.m_size = 0;
    
	}
  
	public boolean add(T item, int threadID) { 
		Node pred, curr;
		int key = item.hashCode();
		
		//lock the list!	
		m_lock.lock();
		
		try {
			pred = m_head;
			curr = pred.m_next;
			
			//search for the first element equal or larger to the new element
			while (curr.m_key < key) {
				pred= curr;
				curr = curr.m_next;
			}
			
			
			if (key == curr.m_key) {
				//element already exist in list - nothing to add
				
				return false;
			} else {
				//add the new element to the list
				Node node = new Node(item);
				node.m_next = curr;
				pred.m_next = node;

				//element added successfully - increment number of elements in list
				m_size++;
        
				return true;
			}
		} finally {
			m_lock.unlock(); //always unlock
		}
	}
  
	public boolean remove(T item, int threadID) {
		Node pred, curr;
		int key = item.hashCode();
		
		//lock the list!	
		m_lock.lock();
		
		try {
			pred = this.m_head;
			curr = pred.m_next;
			
			//search for the first element equal or larger to the element to be removed
			while (curr.m_key < key) {
				pred = curr;
				curr = curr.m_next;
			}
			
			
			if (key == curr.m_key) {
				// remove the element from the list
				pred.m_next = curr.m_next;
        
				//element removed successfully - decrement number of elements in list
				m_size--;
        
				return true;
			} else {
				//element was not found in the list - nothing to remove
				return false;
			}
		} finally {              
			m_lock.unlock();  // always unlock
		}
	}
  
	public boolean contains(T item, int threadID) {
		Node pred, curr;
		int key = item.hashCode();
		
		//lock the list!
		m_lock.lock();
		
		try {
			pred = m_head;
			curr = pred.m_next;
			
			//search for the first element equal or larger to the element we are searching
			while (curr.m_key < key) {
				pred = curr;
				curr = curr.m_next;
			}
			//return true iff found the element in the list
			return (key == curr.m_key);
		} finally {               
			m_lock.unlock(); // always unlock
		}
	}
 

	public void clean(int threadID) {
		
		//lock  the list
		m_lock.lock();
		
		try	{
			//create new tail and set head.next = tail.
			//in that way all other elements are removed because
			//they are no longer reachable from head
			m_head.m_next =  new Node(Integer.MAX_VALUE);
			
			//no elements in the list now
			m_size = 0;
		}
		finally	{
			m_lock.unlock(); //always unlock
		}	
	}

	public boolean isEmpty(int threadID) {
		//if no elements in list that size should be '0'
		return m_size == 0;
	}

	public int size(int threadID) {
		return m_size;
	}

	/**
	 * list Node
	 */
	private class Node {
		/**	
		 * actual item
		 */
		final T m_item;
		
		/**
		 * item's hash code
		 */
		final int m_key;
	
		/**
		 * next Node in list
		 */
		volatile Node m_next;
  
		/**
		 * Constructor for usual Node
		 * @param item element in list
		 */
		Node(T item) {
			this.m_item = item;
			this.m_key = item.hashCode();
		}
  
		/**
		 * Constructor for sentinel Node
		 * @param key should be min or max int value
		 */
		Node(int key) {
			this.m_item = null;
			this.m_key = key;
		}
	}	
}
